//解数独
class Solution {
public:
    bool rowArr[9][10] , colArr[9][10] , grid[3][3][10];
    bool dfs(vector<vector<char>>& board)
    {
        for(int row = 0 ; row < 9 ; ++row)
        {
            for(int col = 0 ; col < 9 ; ++col)
            {
                if(board[row][col] == '.')
                {
                    for(int num = 1 ; num <= 9 ; ++num)
                    {
                        if(!rowArr[row][num] && !colArr[col][num] && !grid[row/3][col/3][num])
                        {
                            board[row][col] = num + '0';
                            rowArr[row][num] = colArr[col][num] = grid[row/3][col/3][num] = true;
                            if(!dfs(board))
                            {
                                board[row][col] = '.';
                                rowArr[row][num] = colArr[col][num] = grid[row/3][col/3][num] = false;
                            }
                            else 
                            {
                                return true;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        for(int i = 0 ; i < 9 ; ++i)
        {
            for(int j = 0 ; j < 9 ; ++j)
            {
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    rowArr[i][num] = true;
                    colArr[j][num] = true;
                    grid[i/3][j/3][num] = true;
                }
            }
        }
        dfs(board);
    }
};

//有效的数独
class Solution {
public:
      bool rowArr[9][10] = {false};
      bool colArr[9][10] = {false};
      bool grid[3][3][10] = {false};
      bool IsLegal(vector<vector<char>> &board,int row,int col)
      {
          int val = board[row][col]-'0';
          if(rowArr[row][val] == true) return false;
          if(colArr[col][val] == true) return false;
          if(grid[row/3][col/3][val] == true) return false;
          return true; 
      }
    bool isValidSudoku(vector<vector<char>>& board) {
       for(int i = 0 ; i < 9 ; ++i)
       {    
           for(int j = 0 ; j < 9 ; ++j)
           {
               if(board[i][j] == '.')continue;
                if(IsLegal(board,i,j) == false) return false;
                else 
                {
                    int val = board[i][j]-'0';
                    rowArr[i][val] = true;
                    colArr[j][val] = true;
                    grid[i/3][j/3][val] = true;
                }
                }
                }
                return true;
    }
};

//N皇后
class Solution {
public:
    vector<bool> dig1;//列
    vector<bool> dig2;//副对角
    vector<bool> dig3;//主对角
    int n;
    bool IsLegal(const vector<string>& chessboard,int row,int col,int n)
    {
        //判断副对角
        if(dig2[row-col+n] == true)
              return false;
        //判断主对角
        if(dig3[row+col] == true)
              return false;
        //判断列
        if(dig1[col] == true)
              return false;
              
        return true;
    }
    int gn;
    vector<vector<string>> ret;
    void dfs(int row)
    {
        if(row == gn)
        {
            ret.push_back(gchessboard);
            return;
        }
        for(size_t i = 0 ; i < gn ; ++i)
        {
            if(IsLegal(gchessboard,row,i,gn))
            {
             gchessboard[row][i] = 'Q';
             //列、主对角、副对角
             dig1[i] = true;
             dig2[row-i+gn] = true;
             dig3[row+i] = true;
             dfs(row+1); 
             //恢复现场
             dig1[i] = false;
             dig2[row-i+gn] = false;
             dig3[row+i] = false;
             gchessboard[row][i] = '.';
            }
        }
    }
    vector<string> gchessboard;
    vector<vector<string>> solveNQueens(int n) {
        gchessboard.resize(n,string(n,'.'));
        dig1.resize(10*n,false);
        dig3 = dig2 = dig1;
        gn = n;
        dfs(0);
        return ret;
    }
};

//优美的排列
class Solution {
public:
    int ret = 0;
    vector<bool> check;
    int gAim;
    void dfs(int pos)
    {
        if(pos > gAim)
        {
            ret++;
            return;
        }
        for(int i = 1 ; i <= gAim ; ++i)
        {
            if(check[i] == false &&(i % pos == 0 || pos % i == 0))
            {
                check[i] = true;
                dfs(pos+1);
                check[i] = false;
            }
        }

    }
    int countArrangement(int n) {
        gAim = n;
        check.resize(20);
        dfs(1);
        return ret;
    }
};

//字母大小写全排列
class Solution {
public:
    vector<string> ret;
    string path;
    void dfs(string s , size_t pos)
    {
        if(path.size() == s.size())
        {
            ret.push_back(path);
            return;
        }
        //如果是数字直接向下层递归
        if(s[pos] >= '0' && s[pos] <= '9')
        {
            path.push_back(s[pos]);
            dfs(s,pos+1);
            path.pop_back();
        }
        else 
        {
            //选择小写
            path.push_back(tolower(s[pos]));
            dfs(s,pos+1);
            path.pop_back();
            //选择大写
            path.push_back(toupper(s[pos]));
            dfs(s,pos+1);
            path.pop_back();
        }
    }
    vector<string> letterCasePermutation(string s) {
        dfs(s,0);
        return ret;
    }
};

//组合总和
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int gtarget = 0;
    void dfs(vector<int>& nums , size_t pos , int sum)
    {
        if(sum == gtarget)
        {
            ret.push_back(path);
            return;
        }
        if(pos == nums.size() || sum > gtarget) return;

        
        for(int k = 0 ; k * nums[pos] <= gtarget ; ++k)
        {
            if(k) path.push_back(nums[pos]);
            dfs(nums,pos+1,sum+k*nums[pos]);
        }

        for(int k = 1 ; k * nums[pos] <= gtarget ; ++k)
        {
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        gtarget = target;
        dfs(candidates,0,0);
        return ret;
    }
};